package com.example.demo.leetcode.difficult;

import java.util.Arrays;

/**
 * 
 * @author xiaoxin
 *
 */
public class Solution {
	public static void main(String[] args) {
		//Solution_1_4.testMethed();
		//Solution_2_10.testMethed();
		
	}
}

/**
 * 题目描述：
 * 	给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * 补充：
 * 	'.' 匹配任意单个字符，'*' 匹配零个或多个前面的那一个元素
 * 	s 可能为空，且只包含从 a-z 的小写字母，p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * @author xiaoxin
 *
 */
class Solution_2_10 {
	public boolean isMatch(String s, String p) {
		
		
		return false;
	}
	public static void testMethed() {
		Solution_2_10 solution = new Solution_2_10();
		String s = "qwertasdf";
		String p = "qwertasdf";
		boolean match = solution.isMatch(s, p);
		System.out.println(match);
	}
}

/**
 * 题目描述：
 * 	给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
 * 示例：
 * 	nums1 = [1, 3]	nums1 = [1, 2]
 *  nums2 = [2]	nums2 = [3, 4]
 *  则中位数是 2.0	则中位数是 (2 + 3)/2 = 2.5
 * 解题思路：
 * 	中位数概念：中位数是按顺序排列的一组数据中居于中间位置的数。
 * 	解题思路则是先排序后取值
 * @author xiaoxin
 *
 */
class Solution_1_4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    	int[] merge = merge(nums1, nums2);
    	System.out.println("合并之后的数组为：" + Arrays.toString(merge));
    	if(merge.length % 2 == 0) {
    		//偶数
    		return (merge[merge.length / 2] + merge[(merge.length / 2) - 1]) / 2.0;
    	} else {
    		//奇数
    		return merge[merge.length / 2];
    	}
    }
    
    public static int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		for (int index = 0, i = 0, j = 0; index < result.length; index++) {
			if (i >= left.length)
				result[index] = right[j++];
			else if (j >= right.length)
				result[index] = left[i++];
			else if (left[i] > right[j])
				result[index] = right[j++];
			else
				result[index] = left[i++];
		}
		return result;
	}

    public static void testMethed() {
    	Solution_1_4 solution = new Solution_1_4();
    	int[] nums1 = {1, 2, 6, 7, 14, 17};
    	int[] nums2 = {13, 14, 15, 19};
    	double findMedianSortedArrays = solution.findMedianSortedArrays(nums1, nums2);
    	System.out.println(findMedianSortedArrays);
    }
}